package arithmetic;

import java.util.Random;
import java.util.Scanner;

/**
 * @Author: Jie
 * @Date: 2019/3/14 18:18
 * @Function :动态规划，就是 动态递推
 * 1、递归 + 记忆化 --> 递推
 * 2、状态的定义 ： opt[n],dp[n],fib[n]
 *     opt 数组
 *     dp 方程
 * 3、状态转移方程： opt[n] = best_of (opt[n-1],opt[n-2],...)
 * 4、最优子结构 （目的：可以有小推大，递推）
 *
 * 斐波那切数列
 */
public class A_24_DynamicProgramming {
    public static void main(String[] args) {

        long t1 = System.currentTimeMillis();
        int i2 = fibDynamic(100000000);
        System.out.println(i2);
        long t2 = System.currentTimeMillis();
        System.out.println("Time is: " + (t2 - t1));

        System.out.println("over");

        fibJuZhen();

    }

    /**
     * 时间复杂度  2的n次方
     * 如果有缓存 可减少复杂度。所有 fib(固定数值)只计算一次
     * 斐波那切数列
     * @param n
     * @return
     */
    public static int fib(int n){
        return n <=1 ? n :fib(n-1) + fib(n-2);
    }

   //优化二：时间复杂度O(N)  空间复杂度O(1)
    public static int fibDynamic (int n){
        int[] F = new int [n + 1];
        F[0] = 0;
        if (n==0)
            return 0;
        F[1] = 1;
        for (int i = 2; i <= n; i++) {
            F[i] = F[i-1] +F[i-2];
        }
        return F[n];
    }

    /**
     * [ fn]    =[1  1] * [fn-1]= [1* fn-1  +  1* fn-2]
     * [ fn-1]   [1  0]   [fn-2]  [1* fn-1  +  0* fn-2]
     *
     * todo y = a的n次幂 * 常亮（f1 f0）,哪里体现了 f1 f0？
     * [f1] =1
     * [f0] =0
     *
     * 转成了
     * [ fn+1]    =[1  1] 的 n 次幂 也就是求
     * [ fn]       [1  0]
     *
     * a 的 n次幂
     * @return
     */
    public static void fibJuZhen(){
        Scanner scanner = new Scanner(System.in);
        while (true) {
            // 第n个斐波那契数,从0开始
            int n = scanner.nextInt();
            System.out.println("fib "+n);
            int i = fibDynamic(n);
            System.out.println("res fibDynamic=="+i +"  ");
            long t1 = System.currentTimeMillis();
            int[][] m = fb(n);
            long t2 = System.currentTimeMillis();
            System.out.println(m[0][1]);
            System.out.println("Time is: " + (t2 - t1));
        }
    }

    // 关联矩阵
    private static final int[][] UNIT = { { 1, 1 }, { 1, 0 } };
    // 全0矩阵
    private static final int[][] ZERO = { { 0, 0 }, { 0, 0 } };
//    private static final int[][] ZERO = { { 1}, { 0 } };
    /**
     * 求斐波那契数列
     *
     * @param n
     * @return
     */
    public static int[][] fb(int n) {
        if (n == 0) {//为了应对n==0,
            System.out.println("zero。。。。。。。。。。。。。。");
            return ZERO;
        }
        if (n == 1) {
            return UNIT;
        }
        // n是偶数
        if ((n & 1) == 0) {
            int[][] matrix = fb(n >> 1);
            return matrixMultiply(matrix, matrix);
        }
        // n是奇数
        int[][] matrix = fb((n - 1) >> 1);
        return matrixMultiply(matrixMultiply(matrix, matrix), UNIT);
    }


    /*矩阵乘法*/
    private static int[][] matrixMultiply(int[][] a, int[][] b){
        int rows = a.length;
        int cols = b[0].length;
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[i].length; k++) {
                    matrix[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return matrix;
    }

}
